package Day2025_03_10;

import java.util.*;

public class LeetCode210 {
    public int[] findOrder(int numCourses, int[][] p) {
        int n = p.length;
        int[] ret = new int[numCourses];
        int k = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] in = new int[numCourses];
        for (int i = 0; i < n; i++) {
            int a = p[i][0], b = p[i][1];
            if (!map.containsKey(b)) map.put(b, new ArrayList<>());
            map.get(b).add(a);
            in[a]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (in[i] == 0) q.add(i);
        while (!q.isEmpty()) {
            int t = q.poll();
            ret[k++] = t;
            for (int x : map.getOrDefault(t, new ArrayList<>())) {
                in[x]--;
                if (in[x] == 0) q.add(x);
            }
        }
        if (k == numCourses) return ret;
        return new int[0];
    }
}
